//
// Created by francklinson on 2021/5/9.
//


#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

class Solution {
public:
    int minDays(vector<int> &bloomDay, int m, int k) {
        auto n = bloomDay.size();
        if (n < m * k) return -1;  // 花不够成足够束
        int right = *max_element(bloomDay.begin(), bloomDay.end());  // 最短的天数是花开时间的最小值
        int left = *min_element(bloomDay.begin(), bloomDay.end());   // 最大的天数是花开时间的最大值
        // 二分确定一个合适的天数
        while (left < right) {
            int mid = (left + right) / 2;
            if (checkValid(bloomDay, mid, m, k)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;


    }

    bool checkValid(vector<int> &bloomDay, int n, int m, int k) {
        /**
         * 检查第n天的开花状态是否满足要求
         */
        vector<int> state(bloomDay.size(), 0);
        for (int i = 0; i < bloomDay.size(); ++i) {
            if (bloomDay[i] <= n) state[i] = 1; // 第n天花开
        }
        // 检查是否足够成束
        // 双指针检查
        int num = 0;
        for (int i = -1, j = 0; j < state.size() and num <= m; ++j) {
            if (state[j] == 0) { // 这朵花不开
                i = j;
            } else { // 这朵花开
                if (j - i == k) { // 足够成一束花
                    i = j;
                    ++num;
                }
            }
        }

        return num >= m;
    }
    // AC 8% ....

};
class Solution2 { // 题解   思路一样 辅助函数更好
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if (k * m > bloomDay.size()) {
            return -1;
        }
        int low = 1, high = 1;
        int length = bloomDay.size();
        for (int i = 0; i < length; i++) {
            high = max(high, bloomDay[i]);
        }
        while (low < high) {
            int days = (high - low) / 2 + low;
            if (canMake(bloomDay, days, m, k)) {
                high = days;
            } else {
                low = days + 1;
            }
        }
        return low;
    }

    bool canMake(vector<int>& bloomDay, int days, int m, int k) { // 辅助函数写得好 不需要额外的数组  单指针就可
        int bouquets = 0;
        int flowers = 0;
        int length = bloomDay.size();
        for (int i = 0; i < length && bouquets < m; i++) {
            if (bloomDay[i] <= days) {
                flowers++;
                if (flowers == k) {
                    bouquets++;
                    flowers = 0;
                }
            } else {
                flowers = 0;
            }
        }
        return bouquets >= m;
    }
};

int main() {
    vector<int> bd{1, 10, 3, 10, 2};
    vector<int> bd2{7, 7, 7, 7, 12, 7, 7};
    vector<int> bd3{1000000000, 1000000000};
    vector<int> bd4{1, 10, 2, 9, 3, 8, 4, 7, 5, 6};
    Solution sol;
    cout << sol.minDays(bd, 3, 1) << endl;
    cout << sol.minDays(bd, 3, 2) << endl;
    cout << sol.minDays(bd2, 2, 3) << endl;
    cout << sol.minDays(bd3, 1, 1) << endl;
    cout << sol.minDays(bd4, 4, 2) << endl;
    return 0;
}